This disclosure relates to combinational circuits, and more specifically to a method of optimizing combinational circuits.
Combinational circuits have many possible applications. One such application is computing an inverse in a Galois Field, which is a field containing a finite number of elements. A combinational circuit is a circuit having an output value determined by the values of its inputs. Combinational circuits can be represented as circuit schematics using Boolean logic gates (such as AND gates and XOR gates), or can be represented mathematically using formulas having operations corresponding to logic gates. For example, an AND gate corresponds to a field multiplication operation, and an XOR gate corresponds to a field addition operation. Logic gates can be arranged to calculate functions, and binary string output of a function may be referred to as a “target signal.” In a typical truth table for a function, the target signal corresponding to the function is the last column of the truth table.
A combinational circuit may have both linear and non-linear portions, where the “non-linear” portions contain AND gates and XOR gates, and the “linear” portions contain only XOR gates. A quantity of AND gates of a combinational circuit may be referred to as the “multiplicative complexity” of the circuit. Combinational circuits and their associated formulas can be extremely large and complex in certain applications, such as microprocessors.